#include <bits/stdc++.h>

using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class BinaryTreeTraversalIteration
{
public:
    // 先序打印所有节点，非递归版
    static void preOrder(TreeNode* head)
    {
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            st.push(head);
            while(!st.empty())
            {
                head = st.top();
                st.pop();
                cout << head->val << " ";
                if(head->right != nullptr) st.push(head->right);
                if(head->left != nullptr) st.push(head->left);
            }
            cout << endl;
        }
    }

	// 中序打印所有节点，非递归版
    static void inOrder(TreeNode* head)
    {
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            while(!st.empty() || head != nullptr)
            {
                if(head != nullptr)
                {
                    st.push(head);
                    head = head->left;
                }
                else
                {
                    head = st.top();
                    st.pop();
                    cout << head->val << " ";
                    head = head->right;
                }
            }
            cout << endl;
        }
    }

	// 后序打印所有节点，非递归版
	// 这是用两个栈的方法
    static void posOrderTwoStacks(TreeNode* head)
    {
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            stack<TreeNode*> collect;
            st.push(head);
            while(!st.empty())
            {
                head = st.top();
                st.pop();
                collect.push(head);
                if(head->left != nullptr) st.push(head->left);
                if(head->right != nullptr) st.push(head->right);
            }
            while(!collect.empty())
            {
                cout << collect.top()->val << " ";
                collect.pop();
            }
            cout << endl;
        }
    }

	// 后序打印所有节点，非递归版
	// 这是用一个栈的方法
    static void posOrderOneStack(TreeNode* head)
    {
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            st.push(head);
            // 如果始终没有打印过节点，head就一直是头节点
			// 一旦打印过节点，head就变成打印节点
			// 之后head的含义 : 上一次打印的节点
            while(!st.empty())
            {
                TreeNode* cur = st.top();
                if(cur->left != nullptr && head != cur->left && head != cur->right)
                {
                    // 有左树且左树没处理过
                    st.push(cur->left);
                }
                else if(cur->right != nullptr && head != cur->right)
                {
                    // 有右树且右树没处理过
                    st.push(cur->right);
                }
                else
                {
                    // 左树、右树 没有 或者 都处理过了
                    cout << cur->val << " ";
                    head = st.top();
                    st.pop();
                }
            }
            cout << endl;
        }
    }

    // 用一个栈完成先序遍历
	// 测试链接 : https://leetcode.cn/problems/binary-tree-preorder-traversal/
    static vector<int> preorderTraversal(TreeNode* head) 
    {
        vector<int> ans;
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            st.push(head);
            while(!st.empty())
            {
                head = st.top();
                st.pop();
                ans.push_back(head->val);
                if(head->right != nullptr) st.push(head->right);
                if(head->left != nullptr) st.push(head->left);
            }
        }
        return ans;
    }

    // 用一个栈完成中序遍历
	// 测试链接 : https://leetcode.cn/problems/binary-tree-inorder-traversal/
    vector<int> inorderTraversal(TreeNode* head) 
    {
        vector<int> ans;
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            while(!st.empty() || head != nullptr)
            {
                if(head != nullptr)
                {
                    st.push(head);
                    head = head->left;
                }
                else
                {
                    head = st.top();
                    st.pop();
                    ans.push_back(head->val);
                    head = head->right;
                }
            }
        }
        return ans;
    }

	// 用两个栈完成后序遍历
	// 提交时函数名改为postorderTraversal
	// 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    static vector<int> postorderTraversalTwoStack(TreeNode* head)
    {
        vector<int> ans;
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            stack<TreeNode*> collect;
            st.push(head);
            while(!st.empty())
            {
                head = st.top();
                st.pop();
                collect.push(head);
                if(head->left != nullptr) st.push(head->left);
                if(head->right != nullptr) st.push(head->right);
            }
            while(!collect.empty())
            {
                ans.push_back(collect.top()->val);
                collect.pop();
            }
        }
        return ans;
    }

	// 用一个栈完成后序遍历
	// 提交时函数名改为postorderTraversal
	// 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    static vector<int> postorderTraversalOneStack(TreeNode* head)
    {
        vector<int> ans;
        if(head != nullptr)
        {
            stack<TreeNode*> st;
            st.push(head);
            // 如果始终没有打印过节点，head就一直是头节点
			// 一旦打印过节点，head就变成打印节点
			// 之后head的含义 : 上一次打印的节点
            while(!st.empty())
            {
                TreeNode* cur = st.top();
                if(cur->left != nullptr && head != cur->left && head != cur->right)
                {
                    // 有左树且左树没处理过
                    st.push(cur->left);
                }
                else if(cur->right != nullptr && head != cur->right)
                {
                    // 有右树且右树没处理过
                    st.push(cur->right);
                }
                else
                {
                    // 左树、右树 没有 或者 都处理过了
                    ans.push_back(cur->val);
                    head = st.top();
                    st.pop();
                }
            }
        }
        return ans;
    }
};


class Solution 
{
public:
	// 测试链接 : https://leetcode.cn/problems/binary-tree-preorder-traversal/
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        if(root)
        {
            stack<TreeNode*> st;
            st.push(root);
            TreeNode* cur = root;
            while(!st.empty())
            {
                // 开始遍历一棵树
                // 1.左路节点进栈
                while(cur)
                {   
                    st.push(cur);
                    ret.push_back(cur->val);
                    cur = cur->left;
                }

                // 访问左路节点的右子树
                TreeNode* top = st.top();
                st.pop();
                cur = top->right;
            }
        }
        return ret;
    }

	// 测试链接 : https://leetcode.cn/problems/binary-tree-inorder-traversal/
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> v;
        if(root)
        {
            stack<TreeNode*> st;
            TreeNode* cur = root;
            while(cur || !st.empty())
            {
                // 1.左路节点入栈
                while(cur)
                {
                    st.push(cur);
                    cur = cur->left;
                }
                // 2.当左路节点出栈时，表示左子树已经访问过了，应该
                // 访问这个节点和它的右子树
                TreeNode* top = st.top();
                st.pop();
                v.push_back(top->val);  // 访问这个节点

                cur = top->right;   // 转化成子问题访问右子树
            }
        }
        return v;
    }

	// 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> v;
        if(root)
        {
            stack<TreeNode*> st;
            TreeNode* cur = root;
            TreeNode* prev = nullptr;
            while(cur || !st.empty())
            {
                // 左路节点入栈
                while(cur)
                {
                    st.push(cur);
                    cur = cur->left;
                }
                TreeNode* top = st.top();   // 取栈顶节点但不pop
                // 栈顶节点右子树为空或者上一次访问的节点是top右子树的根，说明右子树已经访问过了
                // 可以访问栈顶节点，否则转换成子问题访问top的右子树
                if(top->right == nullptr || top->right == prev)
                {
                    st.pop();
                    v.push_back(top->val);
                    prev = top;
                    cur = nullptr;  // cur为空表示弹出的栈顶节点没有右子树或者右子树已经访问过了
                }
                else
                    cur = top->right;
            }
        }
        return v;
    }
};

int main() 
{
    /*
            1
        2       3
      4   5   6    7
    */
    TreeNode* head = new TreeNode(1);
    head->left = new TreeNode(2);
    head->right = new TreeNode(3);
    head->left->left = new TreeNode(4);
    head->left->right = new TreeNode(5);
    head->right->left = new TreeNode(6);
    head->right->right = new TreeNode(7);
    cout << "先序遍历非递归版" << endl;
    BinaryTreeTraversalIteration::preOrder(head);
    cout << "中序遍历非递归版" << endl;
    BinaryTreeTraversalIteration::inOrder(head);
    cout << "后序遍历非递归版 - 2个栈实现" << endl;
    BinaryTreeTraversalIteration::posOrderTwoStacks(head);
    cout << "后序遍历非递归版 - 1个栈实现" << endl;
    BinaryTreeTraversalIteration::posOrderOneStack(head);

    return 0;
}